package leetcode; /**
 * description:
 * author:zt
 * date:2021-07-30
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定一个包含n 个整数的数组nums和一个目标值target，
 * 判断nums中是否存在四个元素 a，b，c和 d，使得a + b + c + d的值与target相等？找出所有满足条件且不重复的四元组。
 *
 * 注意：答案中不可以包含重复的四元组。
 */
public class leetcode18 {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        if (nums == null || nums.length < 4) {
            return ans;
        }
        int len = nums.length;
        for (int i = 0; i < len-3; i++) {
            //去重
            if (i>0 && nums[i]==nums[i-1]) continue;
            //剪枝
            if (nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target) break; //本轮数字nums[i]加上后面最小的三个数字都要比target大
            if (nums[i]+nums[len-1]+nums[len-2]+nums[len-3]<target) continue; //本轮数字nums[i]加上后面最大的三个数字都要比target小

            for (int j = i+1; j < len-2; j++) {
                //去重
                if (j>i+1 && nums[j]==nums[j-1]) continue;
                //剪枝
                if (nums[i]+nums[j]+nums[j+1]+nums[j+2]>target) break; //剪枝同上
                if (nums[i]+nums[len-1]+nums[len-2]+nums[j]<target) continue;
                int L = j+1, R = len-1;
                while (L<R){
                    int sum = nums[i]+nums[j]+nums[L]+nums[R];
                    if (sum==target){
                        ans.add(Arrays.asList(nums[i],nums[j],nums[L],nums[R]));
                        while (L<R && nums[L]==nums[L+1]) L++;
                        while (L<R && nums[R]==nums[R-1]) R--;
                        L++; R--;
                    }
                    else if (sum<target) L++;
                    else if (sum>target) R--;
                }
            }
        }
        return ans;
    }
}
